package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 61. Rotate List
 *
 * Given the head of a linked list, rotate the list to the right by k places.
 *
 * Example 1:
 *  Input: head = [1,2,3,4,5], k = 2
 *  Output: [4,5,1,2,3]
 *
 * Example 2:
 *  Input: head = [0,1,2], k = 4
 *  Output: [2,0,1]
 *
 * Constraints:
 *  The number of nodes in the list is in the range [0, 500].
 *  -100 <= Node.val <= 100
 *  0 <= k <= 2 * 10^9
 */
public class Num_0061 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode rotateRight(ListNode head, int k);

        default void assertExpected(int[] head, int k, int[] expected) {
            if (!assertEquals(rotateRight(build(head), k), build(expected))) {
                rotateRight(build(head), k);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode rotateRight(ListNode head, int k) { // 求链表长度：时O(n) 空O(1)
            /*
             * 旋转链表
             *
             * 链表节点只有 next 指针，需要遍历一次才能知道 k % list.size 的位置
             *    [0,1,2], k=4
             * -> [2,0,1]
             * -> [1,2,0]
             * -> [0,1,2]
             * -> [2,0,1]
             */
            if (head == null) {
                return null;
            }
            int n = 0;
            ListNode cur = head;
            ListNode tail = null;
            while (cur != null) { // 计算链表长度
                n++;
                tail = cur;
                cur = cur.next;
            }
            cur = head;
            if (k % n == 0) { // 不动
                return head;
            }
            int idx = n - 1 - k % n; // 计算需要切割位置的前一个元素位置
            for (int i = 0; i < idx; i++) {
                cur = cur.next;
            }
            ListNode newHead = cur.next;
            cur.next = null;
            tail.next = head;
            return newHead;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[]{}, 0, new int[]{});
        solution.assertExpected(new int[]{1}, 0, new int[]{1});
        solution.assertExpected(new int[]{1,2,3,4,5}, 2, new int[]{4,5,1,2,3});
        solution.assertExpected(new int[]{0,1,2}, 4, new int[]{2,0,1});
    }
}
